package sort;

/**
 * @author Europa
 * @create 2020-05-15 3:47
 */
public class Merge extends Sort {

    /**
     * 归并排序<br/>
     * 可视化 https://www.bilibili.com/video/BV1GW411H76M
     *
     * @param array int数组
     */
    @Override
    public void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    /**
     * 归并排序
     *
     * @param array int数组
     * @param left  起始索引
     * @param right 结束索引
     */
    private void sort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (right + left) / 2;
        sort(array, left, mid);
        sort(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    /**
     * 数组合并
     *
     * @param array int数组
     * @param start 起始索引
     * @param mid   中间索引
     * @param end   结束索引
     */
    private void merge(int[] array, int start, int mid, int end) {
        //开辟额外大集合，设置指针
        int[] temp = new int[end - start + 1];
        int l = start, r = mid + 1, t = 0;
        //比较两个小集合的元素，依次放入大集合
        while (l <= mid && r <= end) {
            if (array[l] <= array[r]) {
                temp[t] = array[l];
                l++;
            } else {
                temp[t] = array[r];
                r++;
            }
            t++;
        }
        //左侧小集合还有剩余，依次放入大集合尾部
        while (l <= mid) {
            temp[t] = array[l];
            t++;
            l++;
        }
        //右侧小集合还有剩余，依次放入大集合尾部
        while (r <= end) {
            temp[t] = array[r];
            t++;
            r++;
        }
        //把大集合的元素复制回原数组
        if (temp.length >= 0) {
            System.arraycopy(temp, 0, array, start, temp.length);
        }
    }


}
